package q668_findKthNumber;

public class Solution_1 {
    /**
     * 考虑一个问题 我们要寻找矩阵中第k小的数 （实际上就是从小到大排名第k个数）
     * 如果无法直接定位 我们可以随机抽出来一个数 random
     * 然后一行一行的考虑 小于等于这个数的个数有多少个 如果遍历完后发现小于等于random的恰好是k个
     * 那么random也就是我们需要的答案
     * 当然 我们不可能通过随机的方式来找到这个数 所以应该使用二分法
     * 每次能够减少一半查找量
     */
    public int findKthNumber(int m, int n, int k) {
        // 首先定义两个边界
        int l = 1, r = m * n;
        while (l < r) {
            // 取出一个数 也就是l和r的中间位置
            // 开始考虑小于等于它的数字有多少个
            int mid = l + ((r - l) >> 1);
            int countLower = 0;
            for (int i = 1; i <= m; i++) {
                // 小于等于mid的数可以通过计算Math.min(mid / i, n)获得
                // 这是因为
                // 1 对于第i行 这一行的每一个数都是i的倍数 所以我们只需要了解 mid / i 为多少
                // 就可以知道这一行小于等于mid的数字有多少个 例如 3 6 9 12。。这一行 小于10的数 用10/3即可
                // 2 由于列n的限制 小于等于mid的数每行最多n个 所以要用math.min
                countLower += Math.min(mid / i, n);
            }
            // 如果发现count比k大 说明我们r取大了 则mid需要向左
            if (countLower >= k) {
                r = mid;
            }else {
                // 否则l小了 mid需要向右
                l = mid + 1;
            }
        }
        // 最后返回到左侧
        return l;
    }
}
